# 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 
# 
#  你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 
# 
#  返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：[7,1,5,3,6,4]
# 输出：5
# 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
#      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
#  
# 
#  示例 2： 
# 
#  
# 输入：prices = [7,6,4,3,1]
# 输出：0
# 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= prices.length <= 105 
#  0 <= prices[i] <= 104 
#  
#  Related Topics 数组 动态规划 
#  👍 1580 👎 0
import math
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]
        max_profit = 0
        for p in prices:
            max_profit = max(p - min_price, max_profit)
            min_price = min(p, min_price)
        return max_profit



# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
设历史低价为min, 则第i天能赚的钱为prices[i] - min
循环, 当天能卖多少钱,是否最大, 当天是否比历史低价低
"""
# def maxProfit(self, prices: List[int]) -> int:
#     min_prices = prices[0]
#     max_profit = 0
#     for p in prices:
#         max_profit = max(p - min_prices, max_profit)
#         min_prices = min(p, min_prices)
#     return max_profit


if __name__ == '__main__':
    s = Solution()
    p1 = [7, 1, 5, 3, 6, 4]
    assert s.maxProfit(p1) == 5, s.maxProfit(p1)
    p2 = [7, 6, 4, 3, 1]
    assert s.maxProfit(p2) == 0, s.maxProfit(p2)
